package book;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class JumpSolution {
    public int jump(int[] arr) {
        int n = arr.length;
        // 保存中间结果: steps[i]保存到达i的最少步数
        int[] steps = new int[n];
        Arrays.fill(steps, -1);
        steps[0] = 0;
        // BFS的核心：使用一个队列保存搜索节点
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            // 首先取出当前点
            int i = queue.poll();
            int s = steps[i];
            // 从当前点搜索，按题意可走1-6步
            for (int j = i + 1; j < n && j <= i + 6; j++) {
                // 目标位置
                int t = j;
                // 判断是否有跳转
                if (arr[t] >= 0) t = arr[t];
                // BFS中第一次搜索到终点就是最优解，可以直接返回
                if (t == n - 1) return s + 1;
                // 计算结果并将目标点保存进队列
                if (steps[t] < 0) {
                    steps[t] = s + 1;
                    queue.offer(t);
                }
            }
        }
        // 队列搜索完毕还没找到终点，说明无解
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {-1, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, -1};
        int ans = new JumpSolution().jump(arr);
        System.out.println("总步数：" + ans);
    }
}

